Exact interval solutions to the discrete Bellman equation and polynomial complexity of problems in interval idempotent linear algebra

摘要

In this note we construct a solution of a matrix interval linear equation ofthe form X=AX+B (the discrete stationary Bellman equation) over partiallyordered semirings, including the semiring of nonnegative real numbers and allidempotent semirings. We discuss also the computational complexity of problemsin interval idempotent linear algebra. In the traditional Interval Analysisproblems of this kind are generally NP-hard. In the note we consider matrixequations over positive semirings; in this case the computational complexity ofthe problem is polynomial. Idempotent and other positive semirings arise naturally in optimizationproblems. Many of these problems turn out to be linear over appropriateidempotent semirings. In this case, the system of equations X=AX+B appears tobe a natural analog of a usual linear system in the traditional linear algebraover fields. B. A. Carre showed that many of the well-known algorithms ofdiscrete optimization are analogous to standard algorithms of the traditionalcomputational linear algebra.